#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-20 10:14 上午
# @Author  : yangdy
# @File    : 2020-07-20.167.两数之和 II - 输入有序数组
# @Software: PyCharmCE
from typing import List


class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        ans = []
        ln = len(numbers)
        # 1.直接枚举 o(n^2) tle
        # for i in range(0, ln-1):
        #     if numbers[i] > target//2:
        #         break
        #     for j in range(i+1, ln):
        #         if numbers[i] + numbers[j] == target:
        #             return [i+1, j+1]
        # 2.枚举+二分搜索 o(nlogn) ok
        # for i in range(0, ln-1):
        #     if numbers[i]*2 > target:
        #         break
        #     l, r, t = i+1, ln-1, target-numbers[i]
        #     while l < r:
        #         h = (l+r)//2
        #         x = numbers[h]
        #         if x == t:
        #             return [i+1, h+1]
        #         elif x < t:
        #             l = h + 1
        #         elif x > t:
        #             r = h - 1
        #     if numbers[l] == t:
        #         return [i+1, l+1]
        # 3.枚举+二分搜索，使用bisect，o(nlogn) ok
        import bisect
        for i in range(ln-1, 0, -1):
            x = numbers.pop()
            j = bisect.bisect_left(numbers, target-x)
            if j != i and numbers[j] == target-x:
                return sorted([i+1, j+1])
        return ans


solve = Solution()

questions = [
    ([2, 7, 11, 15], 9, ),
    ([0, 0, 3, 4], 0,),
    ([5, 25, 75], 100,),
    ([-1, 0], -1,),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print(solve.twoSum(q[0], q[1]))

